\section{Preliminaries on one-dimensional languages}
\label{section:preliminaries_of_one_dimensional_languages}

In this section we recapitulate some definitions of one-dimensional formal languages from \cite{chomsky1956three}. We also describe the Chomsky hierarchy and some properties of their languages. Afterwards, we describe the class of growing context-sensitive languages and its place in the Chomsky hierarchy. 

Let $\Sigma$ be a finite non-empty set of characters. A word over $\Sigma$ is a sequence $w = w_1w_2 \dots w_n$, where $w_i \in \Sigma$ for $1 \leq i \leq n$. The length of a word $w$ is denoted as $|w| = n$. There exists only one word $w$ with $|w| = 0$. This word is called the \emph{empty word} and is denoted as $\lambda$. The set of all words over $\Sigma$ is denoted as $\Sigma^*$ and $\Sigma^+ = \Sigma^* \setminus \{\lambda\}$. 

\begin{definition}
	Let $\Sigma$ be a finite non-empty alphabet. Any subset $L \subseteq \Sigma^*$ is called a formal language. 
\end{definition}

To describe a formal language, there are two main methods: automata and grammars. Whereas automata are used to decide whether a word belongs to a language, grammars are used to generate the words of a language. In this paper, we describe the Chomsky hierarchy by grammars. 

\begin{definition}
	A quadruple $G = (N, T, P, S)$ is called a \emph{grammar}, where 
	
	\begin{compactitem}
		\item $N$ is a finite non-empty set of non-terminals, 
		\item $T$ is a finite non-empty set of terminals ($N \cap T = \emptyset$), 
		\item $P \subseteq N^+ \times (N \cup T)^*$ is a finite set of production rules, and 
		\item $S$ is the start symbol ($S \in N$). 
	\end{compactitem}
\end{definition}

To simplify the notation, we write $\alpha \rightarrow \beta$ for $(\alpha, \beta) \in P$. 

Let $x, y \in (N \cup T)^*$ and $x = w_1lw_2$. We derive $y$ from $x$ if there exists a rule $(l \rightarrow r) \in P$ such that $y = w_1rw_2$. We then write $x \underset{G}{\Rightarrow} y$. As usual, $\overset{*}{\Rightarrow}$ is the reflexive transitive closure of $\Rightarrow$. A string $w \in T^*$ is generated by the grammar $G$, if there exists a derivation such that $S \overset{*}{\Rightarrow} w$. 

\begin{definition}
	Let $G = (V, T, P, S)$ be a grammar. The language generated by this grammar is denoted as \[L(G) = \{w \in T^* \mid S \overset{*}{\Rightarrow} w\}.\]
\end{definition}

If a grammar uses arbitrary rules, it is called \emph{phrase-structure grammar} (PSG) and it generates the class of \emph{phrase-structure languages} ($\familyOf{PSL}$). Chomsky proposed some restrictions on phrase-structure grammars, forming the well-known Chomsky hierarchy. These definitions are from \cite{hopcroft1969formal}.

A grammar is called 
\begin{compactitem}
	\item \emph{monotonic} or \emph{context-sensitive}, if for any rule $(l \rightarrow r) \in P$, $|l| \leq |r|$,
	\item \emph{context-free}, if for any rule $(l \rightarrow r) \in P$, $l \in N$ and
	\item \emph{right-linear}, if for any rule $(l \rightarrow r) \in P$, $l \in N$  and $r = aA$ or $r = a$, where $a \in T$  and $A \in N$. 
\end{compactitem}

The languages generated by the context-sensitive, context-free and right-linear grammars are called the \emph{context-sensitive}, \emph{context-free} and \emph{regular} languages, and the corresponding families of languages are denoted as $\familyOf{CSL}$, $\familyOf{CFL}$ and $\familyOf{RL}$, respectively. 

Since any type of grammar is a restriction of the previous one, we can define the Chomsky hierarchy: 

\begin{definition}
	$\familyOf{RL} \subset \familyOf{CFL} \subset \familyOf{CSL} \subset \familyOf{PSL}$
\end{definition}

If we regard the closure properties of these languages, \cite{ginsburg1967abstract} introduced the definition of an \emph{abstract family of languages} (AFL). If a class of languages is closed under union, concatenation, Kleene-star, $\lambda$-free morphisms, inverse morphisms and intersection with regular sets, this class is called an AFL. \cite{ginsburg1967abstract} examined all of the classes defined above and stated that $\familyOf{PSL}$, $\familyOf{CSL}$, $\familyOf{CFL}$ and $\familyOf{RL}$ are AFLs. 

Now, we describe the growing context-sensitive string languages. We will use this notion in combination with matrix grammars to introduce a new class of picture languages in Section~\ref{section:growing_context-sensitive_matrix_grammars}: the growing context-sensitive matrix languages. The following definition is from \cite{dahlhaus1986membership}:

\begin{definition}
	A string grammar $G = (N, T, P, S)$ is a \emph{growing context-sensitive grammar} (GCSG) where $N$ is a finite set of non-terminals, $T$ is a finite set of terminals, $P$ is a set of production rules and $S$ is the start symbol, where 
	\begin{compactitem}
		\item S does not appear on the right side of any rule and
		\item for any rule $(l \rightarrow r) \in P$, if $l \neq S$, then $|l| < |r|$. 
	\end{compactitem}
\end{definition}

The language generated by a GCSG $G$ is denoted as $L(G)$ and is called a \emph{growing context-sensitive language}. The class of languages generated by GCSG is denoted as $\familyOf{GCSL}$. The growing context-sensitive grammars first appeared in \cite{book1973structure} as a restriction of context-sensitive grammars, where any rule either contains only non-terminals and is length-increasing or generates only one terminal symbol. In \cite{buntrock1996wachsende} we can find a similar definition and a proof, that this definition also generates the class of growing context-sensitive languages. 

\begin{proposition}
	Let $L \in \familyOf{GCSL}$ with $\lambda \not\in L$. Then there exists a grammar $G = (N, T, P, S)$ with $L(G) = L$, which satisfies the following conditions:
	
	\begin{compactitem}
		\item $P \subseteq (N^+ \times N^+) \cup (N \times T)$ and
		\item for all $(l \rightarrow r) \in P$, if $r \in N^+$, then $|l| < |r|$. 
	\end{compactitem}
\end{proposition}

The set of rules only consists of special terminal rules and length-increasing rules containing only non-terminals. In the following we will refer to such a grammar as a \emph{growing context-sensitive grammar with special terminal rules}. 

The class of context-free languages is a proper subset of $\familyOf{GCSL}$, which itself is a proper subset of the context-sensitive languages (see, e.g. \cite{buntrock1996wachsende}).

To characterize the power of growing context-sensitive languages, we continue with an example from \cite{buntrock1996wachsende}, which is not context-free:

\begin{example}
\label{example:growing_context-sensitive}
	Let 	$G = (N, T, P, S)$ be a grammar, where
	
	\begin{compactitem}
		\item $N = \{S, A, E, M, L\}$, 
		\item $T = \{a\}$ and
		\item $
			P = \left\lbrace 
			\begin{matrix}
				S \rightarrow a,  & A \rightarrow AL,   & LE \rightarrow MME, \\
				S \rightarrow aa, & A \rightarrow aa,   & E \rightarrow aa, \\
				S \rightarrow AE, & LM \rightarrow MML, & M \rightarrow aa
			\end{matrix}\right\rbrace$.
	\end{compactitem}
\end{example}

As an example word, we can derive $a^8$ from S as follows: $S \Rightarrow AE \Rightarrow ALE \Rightarrow AMME \Rightarrow aaMME \Rightarrow aaaaME \Rightarrow aaaaaaE \Rightarrow aaaaaaaa$. 

It is obvious that this grammar is growing context-sensitive, since for any rule ${(l \rightarrow r) \in P}$, the right side is strictly longer than the left-hand side, if $l \neq S$. The language generated by the grammar $G$ is $L(G) = \{a^{2^n} \mid n \geq 0\}$. In \cite{buntrock1996wachsende} it is shown that this language is not context-free.That implies that the class of context-free languages is properly included in the class of growing context-sensitive languages. 

\begin{theorem}
	$\familyOf{GCSL}$ is an abstract family of languages. 
\end{theorem}

This theorem has been shown in \cite{buntrock1996wachsende}. Before we introduce our new model, we continue to describe how two-dimensional languages are generated by matrix grammars. 